\section{Problema 3: Transportes pesados}

\subsection{Introducción}

Una empresa que fabrica ladrillos tiene que distribuir su mercadería entre clientes ubicados en distintas ciudades. Las fábricas y las ciudades están unidas por diversas rutas que necesitan repararse debido al efecto del peso de los camiones que circulan sobre ellas. Cada ruta tiene un costo de repavimentación asociado.

El problema consiste en indicar cual es el conjunto mínimo de rutas que necesariamente se deberán reparar para que cada cliente sea abastecido por alguna de las fábricas disponibles.

Por ejemplo:
\begin{verbatim}
INPUT: 
1 2 3
1 2 10
2 3 10
1 3 50

OUTPUT:
20 2 2 3 1 2 
\end{verbatim}

\begin{center}
	\includegraphics[scale=.5]{../pro3bis/tex/ej3-ejemplo.png} \\
	Figura 26: Las aristas en rojo son las que forman parte de la solución.
\end{center}

\subsection{Desarrollo}

Buscando una forma simple y efectiva de modelar el problema actual, consideremos las fábricas y los clientes como diferentes nodos de una estructura que deben ser enlazados entre sí por medio de rutas, las cuales serán representadas por aristas de este nuevo grafo. Cada arista tendrá un peso determinado, que será el mismo que el costo de la ruta correspondiente.

Con este panorama, lo que buscamos encontrar son las aristas de dicho grafo tal que:

\begin{enumerate}
	\item Conecten todos los nodos correspondientes a clientes con algun nodo de tipo fábrica. Es decir, todos los clientes deben ser abastecidos por alguna fábrica.
	\item No conecten nodos ya abastecidos entre sí. El grafo resultante no necesariamente será conexo, sino mas bien un conjunto de grafos conexos, ya que si hay varias fábricas, cada una de ellas pertenecerá a una componente conexa, y los clientes se irán distribuyendo en dichas componentes según los costos de las rutas. Esto es así, ya que si tengo dos componentes conexas que tienen alguna fábrica enlazada, unirlas por medio de una ruta representaría un costo mayor al que ya tenía, e inútil porque ya estaban abastecidas con anterioridad.
	\item No hayan ciclos. En cada componente conexa no debe haber ningún ciclo, ya que estarían conectando dos nodos ya vinculados, algo que solo incrementaría el costo total de manera innecesaria.
	\item La suma de los pesos de las aristas efectivamente elegidas, sea la menor posible.
\end{enumerate}

Entonces, por el primer y tercer item sabemos que estamos buscando algún árbol, que con una mínima cantidad de aristas (para no formar ciclos) conecte un subconjunto de los nodos originales. Si hay mas de una fábrica en la instancia del problema a resolver, por el segundo item sabremos que obtendremos $k$ subconjuntos de nodos (o componentes conexas) en forma de árbol, donde $k$ es igual a la cantidad de fábricas. Es decir, la solución será lo que conocemos como un ``bosque'', cubriendo ahora sí, a todos los nodos existentes en el grafo original. Por último, como en el cuarto item indicamos, estos árboles representarán la manera mas económica de solucionar el problema en conjunto. Entonces estamos frente a un bosque de \emph{arboles generadores minimos}.

Para resolver este problema decidimos usar el \emph{algoritmo de Kruskal}\footnote{ver Cormen, T. and Leiserson, C.E. and Rivest, R.L. and Stein, C., \textsl{Introduction To Algorithms}, MIT-Pess, Cambridge, Massachusets, London, England. Capitulo 6: Graph Algoritm's, Sección 23.2: The algoritms of Kruskal and Prim} frente al de \emph{Prim} y realizar una adaptación del mismo, ya que en sí, directamente comienza con un bosque de árboles. Por lo tanto, la resolución de esta situación especial del problema de \emph{árbol generador mínimo}, es mucho mas intuitiva desde la perspectiva que nos ofrece \emph{Kruskal}. Además, las complejidades temporales en peor caso son equivalentes, por lo tanto no afecta a la decisión. En particular, implementando una serie de mejoras para la implementación de \emph{Kruskal}, se puede reducir mucho mas la cota temporal del algoritmo. Estas mejoras son las dos heurísticas: \emph{union-by-rank} y \emph{path-compression} (analizadas en profundidad en el problema 2 del presente trabajo).

El \emph{algoritmo de Kruskal} consiste básicamente en ir eligiendo las aristas de menor peso de una lista ordenada, de manera que al agregarlas al grafo que representa la solución, no se formen ciclos. Nuestro algoritmo modificado contempla la misma lógica y se describe a continuación:

Las rutas se representarán con la estructura \textit{Ruta}, que contiene el identificador de cada ciudad que conecta y el costo de reparación (es decir, el peso de la arista en el grafo). Necesitaremos tener todas las rutas ordenadas de manera ascendente según dicho costo. Por ello agregamos todas las rutas en un vector y las ordenamos mediante la función \texttt{sort}\footnote{http://www.cplusplus.com/reference/algorithm/sort/} de la librería \texttt{algorithms}.

Luego, tal como hace Kruskal en su implementación optimizada, cada fábrica y cliente (para el algoritmo en principio son nodos indistintos, representados por enteros enumerados) se asocia a un \textsl{Disjoint-set}, es decir, a conjuntos que puedan ser identificados por uno de sus miembros (que está destacado de alguna manera)\footnote{ver Cormen, T. and Leiserson, C.E. and Rivest, R.L. and Stein, C., \textsl{Introduction To Algorithms}, MIT-Pess, Cambridge, Massachusets, London, England. Capitulo 6: Graph Algoritm's, Sección 21.1: Disjoint-set operations}. El \textsl{Disjoint-set} es implementado basicamente por medio de un arreglo de enteros de igual tamaño que la cantidad de nodos totales (es decir, la cantidad de fábricas mas la cantidad de clientes). Cada uno de los índices de dicho arreglo revela quien es el elemento distintivo de la componente conexa a la que pertenece el iésimo nodo. En un principio, cada índice apunta a sí mismo, lo que es representado en particular con el entero $(-1)$. Con el correr del algoritmo, todos los nodos cuyo índice contengan el valor $j$ con $(0 \geq j < n)$ pertenecerán a la componente representada por el j-ésimo nodo, y no se habrá seleccionado ninguna arista que vincule alguno de estos nodos con otro fuera de la componente (osea, un nodo que tenga un índice diferente a $j$).

Hasta ahora, no hemos introducido ningún cambio en la idea general del algoritmo de Kruskal. Los disjoint-sets solo son una manera óptima de implementar dicho algoritmo. Pero recordemos que al unir dos componentes disjuntas, no solo debemos preocuparnos de que no generen ciclos, sino que tampoco debo unir dos componentes que ya tengan fábricas enlazadas a si misma. Por eso es que la clase además utilizará un arreglo de igual tamaño a la cantidad de nodos del grafo original, pero esta vez cada índice nos dirá si el iésimo nodo tiene una fábrica ya agregada en la componente a la cual pertenece. Cada vez que vayamos a unir dos componentes, ademas de consultar si los elementos distintivos son diferentes, deberemos asegurarnos de que al menos uno de las dos no tenga una fábrica ya enlazada. De la misma manera, cuando enlazamos dos conjuntos, tendremos que actualizar este arreglo de manera que el invariante se mantenga. Si la ruta seleccionada cumple con ambos requisitos previamente mencionados, será almacenada en un vector \texttt{solucion} y el costo de la misma será sumado a la variable \texttt{costoSolucion}, que son los datos que necesitamos para resolver el problema.

A continuación se muestra un ejemplo del funcionamiento:

\centerline{\includegraphics[scale=.5]{desarrollo1.png}}

Partimos del grafo original, y seleccionamos la arista de menor valor, en este caso la de valor 2.

\centerline{\includegraphics[scale=.5]{desarrollo2.png}}

Seleccionamos la arista de valor 5, y luego la de valor 8.

\centerline{\includegraphics[scale=.5]{desarrollo3.png}}

Luego, al seleccionar la arista de valor 9, se nos forma un ciclo, por lo que la eliminamos y seguimos el procedimiento.

\centerline{\includegraphics[scale=.5]{desarrollo4.png}}

Elegimos la arista de valor 10. Luego vemos qué pasa con la 15.

\centerline{\includegraphics[scale=.5]{desarrollo5.png}}

Como el cliente 3 ya posee una fábrica, eliminamos la arista 15. Seleccionamos la de valor 20.

\centerline{\includegraphics[scale=.5]{desarrollo6.png}}

Pero la arista 20 forma un ciclo. Por lo que se la elimina, quedándonos con el bosque final.

\subsection{Correctitud}

La demostración de correctitud del algoritmo va a estar dividida en dos grandes partes: que la suma de las rutas seleccionadas es mínima y que todos los clientes tienen algún camino que les permita llegar a una fábrica, es decir, que van a estar abastecidos.

\subsubsection{Suma mínima}

Sabiendo que la lista de aristas $E$ está ordenada de manera ascendente y que $S$ es la solución encontrada por nuestro algoritmo, supongamos entonces que existe otra solución cuya suma total es ligeramente menor gracias a un elemento en los cuales difieren. A esta nueva solución la llamamos $S'$ y consideremos que es igual a $S$ hasta la arista $q \in S$. Ambas soluciones tienen sus elementos ordenados de igual manera que $E$. 

Pretendiendo alcanzar una solución mejor, queremos minimizar la suma de los costos de $S$ modificandola hasta llegar al $S'$ deseado. Si todas las aristas anteriores a $q$ son iguales, las mantenemos idénticas. Ahora, necesitamos cambiar la arista $q$ por otra que me permita mantener unidos todos los nodos del camino al cual pertenece en $S$. Supongamos que existe una arista con estas características, porque de otro modo puede que la arista sea indispensable para unir a alguno de los nodos clientes que induce, pero en ese caso $q$ en realidad debería aparecer también en $S'$ y además en la misma posición que en $S$, ya que provienen del mismo orden que tenemos en $E$. Entonces, como existe, la habremos desechado de $S$ por causar ciclo en éste mismo camino del que hablamos ahora. Por lo tanto, la arista que buscamos la encontraremos en $S$ a la derecha de $q$, entre las aristas descartadas. Ya identificada, la llamamos $p$.

Ahora hacemos el intercambio de aristas, y modifico $S$ eliminando a $q$ y agregando en su lugar a $p$, que era el elemento que anteriormente generaba el ciclo en el camino (Notemos que en realidad, esto podía haber sido logrado con cualquier otra arista que pertenezca a ese mismo camino en $S$). Entonces ahora $p$ es parte de la solución de este nuevo $S'$ cuyo costo es menor que el $S$ original.

Como este intercambio de elementos no afecta a la elección de las aristas que restan a la derecha del $q$ original (Ver \emph{Observación}), las aristas siguientes de $S$ (que consideramos óptimas) se mantienen iguales también en $S'$. De no ser así, repetiremos el proceso de intercambio de elementos hasta lograr que $S$ sea igual al $S'$ buscado, pero recordemos que partimos sabiendo que $S$ y $S'$ solo diferían en un elemento.

Entonces obtenemos que:

\begin{center}
$\sum (S-{q}) = \sum (S'-{p})$
\end{center}

Pero como $S$ estaba ordenado, recordemos que $q \leq p$. Entonces:

\begin{center}
$\sum S \leq \sum S'$
\end{center}

\textbf{Observación:}
\begin{itemize}
\item Sea $C$ un camino de $S$ donde $q \in C$ y sea $C+{p}$ un ciclo en $S$.
\item Sea $x$ una arista de $S$ tal que $x = (u,v)$ donde $u$ es un nodo en $C$ y $v$ no. 
\end{itemize}

Observemos que para todo nodo en $C$ hay mínimo dos aristas que lo inducen ($C$ es un camino, por lo tanto para las aristas intermedias tengo una manera de llegar a un nodo e ir al siguiente), salvo para el par de nodos inducidos por $p$, ya que $p \notin C$. Por lo tanto si en $S'$ agrego $p$, ahora esos nodos también tendrán dos aristas que como mínimo los cubrirán. Luego al eliminar $q$, sigo cubriendo a los mismos nodos de $C$ en $S$, ya que cada uno de los nodos inducidos por $q$ tenía otra arista de $C$ que lo inducía también.

Por lo tanto sigo teniendo un camino viable para alcanzar cualquiera de los nodos que ya podía alcanzar antes. Entonces para toda arista $x \in S$ con las características dichas, nada le impide seguir cubriendo a $u$ en $S'$.

De esta manera podemos ver que modificar la elección de aristas en un ciclo, no modifica la elección de las otras aristas elegidas (si es que son las óptimas desde un principio, frente a la nueva situación lo seguirán siendo).

\subsubsection{Todos los clientes tienen una fábrica}

Siendo $V$ el conjunto de nodos y $E$ el conjunto de aristas del grafo actual. Sabemos que en la iteración iésima tenemos una solución parcial $S$ que es un conjunto de caminos (no circuitos) de varias longitudes, construidos con aristas pertenecientes a $E$. Estos caminos cubren todos los nodos de $V$ (aquellas componentes conexas que solo contienen un nodo en la presente iteración, son considerados caminos de longitud cero).

Por otro lado, nos quedan $m-1$ aristas para analizar. La arista iésima la llamaremos $x = (u,w)$, y podrá ser agregada o no. Uno de los motivos para ser descartada es si $u$ y $w$ ya son inducidos por algún camino de $S$ (sino formaríamos un ciclo o circuito). Notemos que en este caso no dejamos afuera de la solución ningún nodo, ya que justamente ambos nodos ($u$ y $w$) ya habían sido conectados a algún camino que formará parte de la solución. Si este camino aún no fue abastecido, próximamente alcanzaremos una arista de $E$ que lo haga (ya que nuestro grafo original no tiene nodos aislados).

El otro motivo para descartar $x$ es si $u$ y $w$ ya están abastecidos y/o son fábricas. Esto es porque ésta arista solo incrementaría la suma total de manera innecesaria, ya que ambos nodos tienen algún camino disponible hacia alguna fábrica o en particular, son una de ellas. Por lo tanto cuando conectemos este camino a otro, será por medio de una de las aristas siguientes en $E$, que lo vincule a otro camino que no sea una fábrica y tampoco haya sido abastecido.

Si finalmente la arista $x$ se agrega a la solución, es porque conecta dos caminos diferentes y no abastece caminos ya abastecidos. De esta manera, repetimos el proceso hasta analizar todas las aristas de $E$. De ésta manera nos aseguramos que todos los nodos serán cubiertos por algún camino que tenga entre sus nodos a una única fábrica. Lo que sí podría suceder es que queden fábricas aisladas sin conectarse con ningún cliente, ya que éstos pueden llegar a abastecerse de una manera óptima por medio de un camino a otra fábrica.

\subsection{Análisis de complejidad}\label{complejidad3}

\subsubsection{Pseudocódigo}

Sean $m$ la cantidad de rutas y $n$ la cantidad de nodos (la cantidad de fábricas más la cantidad de clientes), el pseudocódigo del algoritmo con su complejidad es el siguiente:

\begin{algorithm}

    \SetKwInOut{Input}{input}
    \SetKwInOut{Output}{ouput}
    \SetKwComment{Complejidad}{\color{Blue}$\rhd$ $\mathcal O($}{\color{Blue}$\mathcal )$}
    \SetKwComment{SubComplejidad}{\color{Red}$\square$ $\mathcal O($}{\color{Red}$\mathcal )$}
    \SetKwComment{SubSubComplejidad}{\color{Fuchsia}$\fullmoon$ $\mathcal O($}{\color{Fuchsia}$\mathcal )$}
    \SetKwComment{ComplejidadTotal}{\color{Blue}Complejidad total $\rhd$ $\mathcal O($}{\color{Blue}$\mathcal )$}
    \SetKwComment{SubComplejidadTotal}{\color{Red}Complejidad total $\square$ $\mathcal O($}{\color{Red}$\mathcal )$}
    \SetKwComment{SubSubComplejidadTotal}{\color{Fuchsia}Complejidad total $\fullmoon$ $\mathcal O($}{\color{Fuchsia}$\mathcal )$}

    \SetKwData{A}{A}
    \SetKwData{n}{n}

    %~ \Input{Vector de ruta \texttt{rutas}, Entero \texttt{fabricas}, Entero \texttt{clientes}}
    %~ \Output{Vac\'io}
    % \BlankLine
    ordenar las aristas de $rutas$ por costo ascendente \Complejidad*[r]{\color{blue}$m*log(m)$}
    crear el disjoint-set que almacenará los nodos \Complejidad*[r]{\color{blue}$n$}
    \For(\Complejidad*[f]{\color{blue}$m$}){cada arista $r$ en $rutas$} {
		buscar los elementos distintivos del par de nodos que conecta $r$ \Complejidad*[r]{\color{blue}$log(n)$}
		unir los conjuntos si son elementos diferentes y al menos uno no tiene una fábrica \Complejidad*[r]{\color{blue}$1$}
		\If{la unión se concretó} {
			agregar la arista $r$ a la solución parcial $r$ \Complejidad*[r]{\color{blue}$1$}
			sumar el costo de la arista $r$ a la suma parcial $r$ \Complejidad*[r]{\color{blue}$1$}
		}\Else{descartar $r$ y continuar con la próxima arista de $rutas$ (si existe) \Complejidad*[r]{\color{blue}$1$}}
    }
    
    \caption{Ejercicio 3 - Resolver::buscarSolucion()}
    \label{pseudocodigo1}
\end{algorithm}

\subsubsection{Análisis}

Como podemos observar en el pseudocódigo previo, la complejidad del algoritmo depende fuertemente de la manera en que ordenamos las aristas del grafo. Como nosotros utilizamos la función \texttt{sort} de la \emph{STL}, la misma nos indica que su complejidad es del orden $O(m*log(m))$. Siendo $m$ la cantidad de aristas del grafo, sabemos que como máximo podremos tener $\frac{n * (n-1)}{2}$ aristas. Acotamos entonces por $m < n^2$. De esta manera, la complejidad de ordenar las aristas resulta ser $O(m*log(m)) \subset O(m*log(n^2))$. Aplicando las propiedades del logaritmo, concluímos que:

\begin{center}
$O(m*log(n^2)) \subset O(m*(log(n) + log(n))) \subset O(m*2log(n)) \subset O(m*log(n))$
\end{center}

Luego tenemos la creación del disjoint-set, que al instanciar arreglos de tamaño $n$, su complejidad será lineal a la cantidad de nodos del grafo. Posterior a esto, por cada arista buscaremos los nodos que representan a cada uno de los extremos de la misma. Como por medio de las heurísticas implementadas logramos que los árboles de relaciones entre nodos sean balanceados y de poca altura, en el caso promedio la complejidad se amortiza lo suficiente como para lograr un tiempo constante. En el peor caso, obtendremos un árbol balanceado donde recorrer la altura completa del mismo nos costará $O(log(n))$. Después, unir ambos conjuntos no es mas que modificar los arreglos correspondientes de manera constante, por eso la complejidad es $O(1)$ (además de guardar los datos necesarios para la solución, que también requieren un tiempo constante). Al repetirse este proceso tantas veces como aristas tengamos en el grafo, tenemos que multiplicar la complejidad obtenida por $m$.

\begin{center}
$O(m*log(n)) + O(n) + (m* O(log n)) \subset 2 * O(m*log(n)) \subset O(m*log(n))$
\end{center}

\subsection{Análisis de casos}

Caso 1) una fábrica y un cliente.

Este caso es trivial, se elije la única arista posible.

\begin{verbatim}
INPUT:
1 1 1  
1 2 10

OUTPUT:
10 1 1 2 
\end{verbatim}

\begin{center}
	\includegraphics[scale=.5]{casoprueba2.png}
\end{center}

Caso 2) menos fábricas que clientes.

Este es el caso promedio, puede generarse un árbol generado mínimo que cubra todos los nodos del grafo original o pueden quedar fábricas desconectadas y de esa manera encontrar un bosque de árboles generadores.

\begin{verbatim}
INPUT:
2 4 9
1 2 10
1 3 6
1 4 4
1 5 4
1 6 3
2 4 8
2 6 2
3 4 1
4 6 3

OUTPUT:
10 4 3 4 2 6 4 6 1 5 
\end{verbatim}

\begin{center}
	\includegraphics[scale=.5]{casoprueba1.png}
\end{center}

Caso 3) todas las aristas con mismo peso.

En estas situaciones, el árbol generador mínimo elegido dependerá del orden en el cual se ubican las aristas luego de efectuar el \texttt{sort} dentro del algoritmo.

\begin{verbatim}
INPUT:
1 2 3
1 2 5
1 3 5
2 3 5

OUTPUT:
10 2 1 2 1 3 
\end{verbatim}

\begin{center}
	\includegraphics[scale=.5]{casoprueba3.png}
\end{center}

\subsection{Test de performance}

Recordemos que la implementación de nuestra versión modificada del algoritmo de Kruskal utiliza dos heurísticas: \emph{path compression} y \emph{union by rank}. Las mismas, como se ha visto con anterioridad, maximizan la optimización del algoritmo, disminuyendo el tiempo empleado para devolver un resultado. Esto se puede apreciar con notoriedad en el siguiente gráfico:

\begin{center}
	\includegraphics[scale=.7]{../pro3bis/tex/comparativaCompletoLineal.png} \\
	Figura 27: Complejidad temporal en grafos completos - Escala lineal
\end{center}

En el gráfico observamos los tiempos necesarios para resolver instancias de hasta 100 nodos (donde el $20\%$ de los mismos son fábricas) y con todas las rutas posibles entre los mismos. Es decir, trabajamos con grafos completos. Las instancias aleatorias fueron creadas con un script hecho en Python. A su vez los tiempos fueron medidos con la librería de C \texttt{times.h}. 

Vemos que la diferencia entre los tiempos medidos y la cota estimada se hace cada vez mas grande, y si bien se observa que los tiempos son fácilmente acotados, deja de percibirse el orden al que pertenecen los tiempos reales. Esto en gran medida se debe a la escala utilizada en el gráfico realizado. Dejamos de lado la escala lineal por la logarítmica (en base 2), y los siguientes son los resultados obtenidos:

\begin{center}
	\includegraphics[scale=.7]{../pro3bis/tex/comparativaCompleto.png} \\
	Figura 28: Complejidad temporal en grafos completos - Escala logarítmica
\end{center}

En esta oportunidad, la diferencia entre ambas funciones se aprecia mejor, así también se puede ver como el orden de los tiempos medidos graficamente es muy similar al orden estimado.

\subsection{Código Fuente}

Incluimos a continuación las principales funciones del programa:

\begin{verbatim}
void Resolver::buscarSolucion() {
    /* ordenar ascendentemente el vector ``rutas'' por el costo de las aristas */
    sort(rutas.begin(), rutas.end(), compararRutas);

    /* crear el disjoint-set */
    DisjointSet ds(cantFabricas, cantClientes);

    /* para cada arista, desde la mínima... */
    for(vector<Ruta>::const_iterator it = rutas.begin(); it != rutas.end(); it++) {
        /* consultar si pertenecen a conjuntos disjuntos diferentes */
        if(ds.unir(ds.padre(it->ciudad_inicio), ds.padre(it->ciudad_fin))) {
            /* agregamos la arista actual a la solución y sumamos el costo */
            solucion.push_back(*it);
            costoSolucion += it->longitud;
        }
    }
}

int DisjointSet::padre(int i) {
    /* crear la lista ``valores'' */
    list<int> valores;

    /* mientras no se encuentre quien es el elemento distintivo,
    guardar en ``valores'' todos los nodos del recorrido  */
    while(links[i] != -1) {
        valores.push_back(i);
        i = links[i];
    }

    /* realizar ``path-compression'' */
    for(list<int>::const_iterator it = valores.begin(); it != valores.end(); it++) {
        links[*it] = i;
    }

    /* devolver el nodo que representa al presente elemento */
    return i;
}

bool DisjointSet::unir(int i, int j) {
    /* no se pueden unir conjuntos que formen ciclos y que ya tengan fabricas */
    if(i == j || (tieneFabrica[i] && tieneFabrica[j])) {
        return false;
    }

    /* si se pueden unir, hacerlo con ``union-by-rank'' */
    if(ranks[i] > ranks[j]) {
        links[j] = i;
    } else {
        links[i] = j;
        if(ranks[i] == ranks[j])
            ranks[j] = ranks[i] + 1;
    }

    /* actualizar el estado del arreglo ``tieneFabrica'' */
    if (tieneFabrica[i]) {
        tieneFabrica[j] = 1;
    } else {
        tieneFabrica[i] = 1;
    }
    return true;
}

\end{verbatim}
